#
# CS 143
#
# This file provides the Routes and RoutingTable class definitions.
#
# @author Henry Li
#

import copy

class Routes:
    '''Routes Data Structure
    The Routes data structure provides a convenient method of storing and
    retrieving IP/Subnet to NIC mappings. We can use this data structure
    as follows, assuming `ip` is a 4-tuple representing the IP address,
    `subnet` is a 4-tuple representing the subnet mask, and `nic` is the
    NIC object.

    Setting an IP/Subnet to NIC mapping:
        routes[(ip, subnet)] = nic

    Retrieving the (NIC, best match IP/Subnet) associated with a particular IP:
        routes[ip]

    Retrieving all the IP/Subnets associated with a NIC:
        routes.getIPSubnets(nic)

    Deleting an IP/Subnet to NIC mapping:
        del routes[nic] 
            -or- 
        del routes[(ip, subnet)]

    Iterating through all the mappings:
        for ((ip, subnet), nic) in routes:
            ...

    '''

    def __init__(self):
        '''Routes class constructor.

        '''
        # dict __table
        # Keys are (ip, subnet), where ip and subnet are (int, int, int, int)
        # Values are NIC objects.
        self.__table = {}

    def __copy__(self):
        '''Shallow copy.
        Creates a shallow copy of the routes object.

        Output:
            A new routes object.

        '''
        routes = Routes()
        routes.__table = copy.copy(self.__table)
        return routes

    def __iter__(self):
        '''Implement iterator functionality.

        '''
        return self.__table.iteritems()
        
    def __setitem__(self, (ip, subnet), nic):
        '''Implement bracket mutator functionality.

        Input:
            (ip, subnet): tuple where
                ip: 4 tuple representing an IP address
                subnet: 4 tuple representing a subnet mask
            nic: NIC associated with this mapping.

        '''
        self.__table[(ip, subnet)] = nic

    def __getitem__(self, ip_request):
        '''Implement bracket accessor functionality.

        Input:
            ip_request: 4 tuple representing an IP address

        Output:
            (nic, (ip, subnet)) tuple where:
                nic: NIC object that best matches the given ip_request
                ip: 4 tuple representing the best match IP address
                subnet: 4 tuple representing the best match subnet mask

        '''
        # Find correct route (most matching bits)
        if self.__table:
            (count, ip_subnet) = max(self.__compare_ip(ip_request, ip_subnet) \
                                     for ip_subnet in self.__table.iterkeys())

            return (self.__table[ip_subnet], ip_subnet) if ip_subnet else None
        
    def __delitem__(self, lookup):
        '''Implement del functionality.
        Given either an IP/Subnet tuple or a NIC, removes all associated
        mappings.

        Input:
            lookup: (ip, subnet) tuple where:
                        ip: 4 tuple representing an IP address
                        subnet: 4 tuple representing a subnet mask
                        - or-
                    nic: NIC object

        '''
        if type(lookup) is tuple:
            del self.__table[lookup]
        else:
            for ip_subnet in self.getIPSubnets(lookup):
                del self.__table[ip_subnet]

    def __compare_ip(self, ip_request, (ip, subnet)):
        '''Compare IP matching within a subnet.
        Given an IP within the context of an IP/Subnet, returns the number 
        of bits that match if the IP falls within the subnet.

        Input:
            ip_request: 4 tuple representing an IP address
            (ip, subnet) tuple where:
                ip: 4 tuple representing an IP address
                subnet: 4 tuple representing a subnet mask
        
        Output:
            (rank, (ip, subnet)) tuple where:
                rank: int representing the match ranking of the given IP.
                ip: 4 tuple representing input IP address
                subnet: 4 tuple representing input subnet mask

        '''
        for i in range(len(ip)):
            # Require exact match with mask to fall in subnet else bad route
            if (subnet[i] & ip[i]) != (subnet[i] & ip_request[i]):
                return (0, None)
        return (self.__count_bits(subnet), (ip, subnet))

    def __count_bits(self, subnet):
        '''Count the set bits in a subnet.
        Given a subnet mask, count the number of set bits.

        Input:
            subnet: 4 tuple representing a subnet mask
        
        Output:
            The number of set bits in `subnet`.

        '''
        count = 0
        for num in subnet:
            while num:
                count += 1
                num &= (num - 1)
        return count

    def getIPSubnets(self, nic):
        '''Get the IP/Subnet mappings associated with a given NIC.

        Input:
            nic: NIC object.
        
        Output:
            A list of (ip, subnet) tuples that are mapped to given 
            `nic`.

        '''
        ip_subnets = []
        for (ip_subnet, dict_nic) in self.__table.iteritems():
            if dict_nic == nic:
                ip_subnets.append(ip_subnet)
        
        return ip_subnets

class RoutingTable:
    '''RoutingTable Data Structure
    The RoutingTable data structure provides a wrapper for the Routes
    object that also takes into account costs for any given IP/Subnet.
    We can use this data structure as follows, assuming `ip` is a 4-tuple
    representing the IP address, `subnet` is a 4-tuple representing the subnet
    mask, `nic` is the NIC object, `cost` is a float, nextHopIP is a 4-tuple
    representing an IP address, and lastUpdateTime is a float.
    
    Setting a table entry:
        routingTable[(ip, subnet)] = (nic, cost, nextHopIP, lastUpdateTime)

    Retrieving the NIC, cost, nextHopIP, lastUpdateTime associated with
    reaching a particular IP:
        routingTable[ip]

    Iterating through all the mappings:
        for ((ip, subnet), cost) in routingTable:
            ...

    Checking for the existence of a table entry:
        if (ip, subnet) in routingTable:
            ...

    Deleting a table entry:
        del routingTable[nic]

    Displaying the routing table:
        print routingTable

    '''
    
    def __init__(self):
        '''RoutingTable class constructor.

        '''
        # Routes routes
        # Backend data structure for storing IP/Subnet to NIC mappings.
        self.routes = Routes()

        # dict costs
        # Mapping between IP/Subnet and cost.
        self.costs = {}
        
        # dict next_hops
        # Mapping between IP/Subnet and IP of the next router.
        self.next_hops = {}
        
        # dict update_times
        # Mapping between IP/Subnet and time this entry was last updated 
        # by its owner
        self.update_times = {}

    def __len__(self):
        '''Length of the routing table.

        Output:
            The length of the routing table.
        '''
        return len(self.costs)
    
    def __copy__(self):
        '''Shallow copy.
        Creates a shallow copy of the routing table object.

        Output:
            A new routing table object.

        '''
        table = RoutingTable()
        table.routes = copy.copy(self.routes)
        table.costs = copy.copy(self.costs)
        table.next_hops = copy.copy(self.next_hops)
        table.update_times = copy.copy(self.update_times)
        return table

    def __str__(self):
        '''Stringify the routing table.
        Converts the routing table into a human readable format.

        Output:
            A string of the routing table entries.
        
        '''
        result =  'IP/Subnet                         Outgoing NIC      Cost\n'
        result += '--------------------------------------------------------\n'
        for ((ip, sub), cost) in self.costs.iteritems():
            result += '%03d.%03d.%03d.%03d/%03d.%03d.%03d.%03d | ' % (ip + sub)
            result += '%03d.%03d.%03d.%03d | ' % self.routes[ip][0].getIP() 
            result += '%0.2f' % cost
            result += '\n'
        return result
    
    def __iter__(self):
        '''Implement iterator functionality.

        '''
        return self.costs.iteritems()

    def __contains__(self, (ip, subnet)):
        '''Implements contains functionality.
        Check whether (ip, subnet) in routing table.

        Input:
            (ip, subnet): tuple where
                ip: 4 tuple representing an IP address
                subnet: 4 tuple representing a subnet mask
        
        Output:
            Boolean of whether the table contains the entry.

        '''
        return (ip, subnet) in self.costs

    def __setitem__(self, (ip, subnet), (nic, cost, next_hop, update_time)):
        '''Implement bracket mutator functionality.

        Input:
            (ip, subnet): tuple where
                ip: 4 tuple representing an IP address
                subnet: 4 tuple representing a subnet mask
            (nic, cost, next_hop, update_time): tuple where
                nic: NIC object
                cost: float
                next_hop: 4 tuple representing an IP address
                update_time: float
        
        '''
        self.routes[(ip, subnet)] = nic
        self.costs[(ip, subnet)] = cost
        self.next_hops[(ip, subnet)] = next_hop
        self.update_times[(ip, subnet)] = update_time

    def __getitem__(self, ip):
        '''Implement bracket accessor functionality.

        Input:
            ip: 4 tuple representing an IP address

        Output:
            (nic, cost, next_hop) tuple where:
                nic: NIC object
                cost: float
                next_hop: 4 tuple representing an IP address
                update_time: float

        '''
        lookup = self.routes[ip]
        if lookup:
            nic, ip_subnet = lookup
            cost = self.costs[ip_subnet]
            next_hop = self.next_hops[ip_subnet]
            update_time = self.update_times[ip_subnet]
            return (nic, cost, next_hop, update_time)

    def __delitem__(self, nic):
        '''Implement del functionality.
        Given a NIC, removes all table entries associated with the NIC.
        
        Input:
            nic: a NIC object.
        
        '''
        ip_subnets = self.routes.getIPSubnets(nic)
        for ip_subnet in ip_subnets:      
            del self.routes[ip_subnet]
            del self.costs[ip_subnet]
            del self.next_hops[ip_subnet]
            del self.update_times[ip_subnet]
